//============================================================================
// Name        : GSP295_Wk6_ShortestPath
// Author      : Ronald Ram
// Version     :
// Copyright   : GSP295 Wk6 Program - Shortest Path
// Description : Implementation of Shortest Path using Graph in C++
//============================================================================



#include<iostream>
#include <string>
#include <vector>
#include "Graph.h"

using namespace std;
using namespace GSP295_Wk6;

//Method Declarations
void WelcomeMsg();
void Instructions();
void InstructionsTest();
void Command(char input);
void AddVertex();
void AddEdge();
void GetWeight();
void GetAdjacentVertices();
void FindPath();
void ClearGraph();
void Print();
void Test();
void Test1();
void Test2();
void Test3();


bool quit = false; 
char addInsertV_InsertE_fWeight_fPath_Clear_pGraph_Quit;
string input;
int weight = 0;

Graph *program;

int main()
{
	WelcomeMsg();

	program = new Graph();
	Test();

	do {
		InstructionsTest();
		cout << "Enter Command: "; cin >> addInsertV_InsertE_fWeight_fPath_Clear_pGraph_Quit;
		system("cls");

		Command(addInsertV_InsertE_fWeight_fPath_Clear_pGraph_Quit);

	} while ( !quit );

	delete [] program;

	cout << "\n\n....Good Bye\n" << endl;
	cin.get(); //system("pause");
	return 0;
}


//Welcome Message
void WelcomeMsg()
{
	cout << "\n**************************************************" << endl;
	cout << "\t GSP295 Week 6: iLab Assignments" << endl;
	cout << "\n\t Title: Graph - Program" << endl;
	cout << "\n\t Author: Ronald Ram" << endl;
	cout << "**************************************************\n\n\n" << endl;
}


//Instructions for Command keys to use
void Instructions()
{
	cout << "----------------------------------------------------" << endl;
	cout << "Command Options: " << endl;
	cout << "----------------------------------------------------" << endl;
	cout << "Add Vertex[V] - Add Edge[E] - Find Weight[W]" << endl << endl;
	cout << "Adjacent Vertices[A] - Find Path[F] - Clear[C]" << endl << endl; 
	cout << " Print Graph[P] - Quit[Q]" << endl;
	cout << "----------------------------------------------------\n" << endl;
}

//Instructions for Command keys to use
void InstructionsTest()
{
	cout << "----------------------------------------------------" << endl;
	cout << "Command Options: " << endl;
	cout << "----------------------------------------------------" << endl;
	cout << "Test One[1] - Test Two[2] - Test Three[3]" << endl << endl; 
	cout << " Print Graph[P] - Quit[Q]" << endl;
	cout << "----------------------------------------------------\n" << endl;
}


//Decide on which command to trigger
void Command(char input)
{
	if      ( input == 'V' || input == 'v' ) { AddVertex();
	} 
	else if ( input == 'E' || input == 'e' ) { AddEdge();
	}
	else if ( input == 'W' || input == 'w' ) { GetWeight();
	}
	else if ( input == 'A' || input == 'a' ) { GetAdjacentVertices();
	}
	else if ( input == 'F' || input == 'f' ) { FindPath();
	}
	else if ( input == 'C' || input == 'c' ) { ClearGraph();
	}
	else if ( input == 'P' || input == 'p' ) { Print();
	}
	else if ( input == 'Q' || input == 'q' ) { quit = true;
	}
	else if ( input == '1' ) { Test1();
	}
	else if ( input == '2' ) { Test2();
	}
	else if ( input == '3' ) { Test3();
	}
}

//Add a Vertex to Array - all Vertices must be unique
//Post: If array is not full, Vertex is added and returns T/F
void AddVertex()
{
	cout << "\nEnter a string: "; cin >> input;

	bool success = false;
	Vertex temp;
	temp.Assign(input, false);

	success = program->AddVertex(temp);

	if ( !success ) 
	{
		cout << "\nVertex Successfully Added to Graph\n\n" << endl;
	} 
	else 
	{
		if ( program->isFull() ) { cout << "\nFailed to add Vertex - Graph is Full\n\n" << endl;
		} 
		else { cout << "\nFailed to add Vertex - already exists in Graph\n\n" << endl; }
	}
}

//Add an Edge between 2 Vertex 
//Pre: User must specify To/From Vertices
//Post: If Vertices are found, Edge weight is added and returns T/F
void AddEdge()
{
	Vertex to, from;

	cout << "\nEnter Start Vertex: "; cin >> input;
	from.Assign(input, false);
	cout << "\nEnter End Vertex: "; cin >> input;
	to.Assign(input, false);
	cout << "\nEnter Edge Weight: "; cin >> weight;

	bool success = program->AddEdge(from, to, weight);

	if ( success ) { cout << "\nEdge Successfully Added to Graph\n\n" << endl;
	} 
	else { cout << "\nFailed to add Edge - no match found\n\n" << endl; }
}

void GetWeight()
{
	Vertex to, from;

	cout << "\nEnter Start Vertex: "; cin >> input;
	from.Assign(input, false);
	cout << "\nEnter End Vertex: "; cin >> input;
	to.Assign(input, false);

	int weight = program->WeightIs(from, to);

	if ( weight == -1 ) { cout << "\nNo Edge Exists between the 2 Vertices\n\n" << endl;
	} 
	else 
	{ 
		cout << "\nThe Weight of Edge, between Vertices [" << from.data << ", " << to.data << "] = " << weight << "\n\n" << endl; 
	}
}

//Find Adjacent Vertices to a vertex
//Pre: Method takes input of vertex to use as root of search
//Post: Method prints out a list of Adjacent Vertices, if any found
void GetAdjacentVertices()
{
	Vertex root;
	cout << "\nEnter Search Vertex: "; cin >> input;
	root.Assign(input, false);

	program->GetToVertices(root);
}

//Clear the graph => both the vertexList and Adjacency Matrix
void ClearGraph()
{
	program->MakeEmpty();

	if ( program->isEmpty() ) 
	{
		cout << "\n\nGraph Successfully Cleared" << endl << endl;
	} 
	else { cout << "\n\nGraph Failed to Clear" << endl << endl; }
}

//Find path btw two Vertices and print results, if any found
void FindPath()
{
	Vertex to, from;

	cout << "\nEnter Start Vertex: "; cin >> input;
	from.Assign(input, false);
	cout << "\nEnter End Vertex: "; cin >> input;
	to.Assign(input, false);

	//program->DFS(from, to);
	program->DFS(from, to);
}

//Print Vertices Array and Adjacency Matrix
void Print()
{
	cout << "\n============================================\n" << endl;
	program->Print();
	cout << "\n============================================\n" << endl;
}

void Test()
{
	//Add Vertices...
	program->AddVertex( Vertex("atl", false) );
	program->AddVertex( Vertex("aus", false) );
	program->AddVertex( Vertex("chi", false) );
	program->AddVertex( Vertex("dal", false) );
	program->AddVertex( Vertex("den", false) );
	program->AddVertex( Vertex("hou", false) );
	program->AddVertex( Vertex("wa", false) );

	//Add Edges...
	program->AddEdge( Vertex("atl", false), Vertex("atl", false), 0 );
	program->AddEdge( Vertex("atl", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("atl", false), Vertex("chi", false), 0 );
	program->AddEdge( Vertex("atl", false), Vertex("dal", false), 0 );
	program->AddEdge( Vertex("atl", false), Vertex("den", false), 0 );
	program->AddEdge( Vertex("atl", false), Vertex("hou", false), 800 );
	program->AddEdge( Vertex("atl", false), Vertex("wa", false), 600 );
	//
	program->AddEdge( Vertex("aus", false), Vertex("atl", false), 0 );
	program->AddEdge( Vertex("aus", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("aus", false), Vertex("chi", false), 0 );
	program->AddEdge( Vertex("aus", false), Vertex("dal", false), 200 );
	program->AddEdge( Vertex("aus", false), Vertex("den", false), 0 );
	program->AddEdge( Vertex("aus", false), Vertex("hou", false), 160 );
	program->AddEdge( Vertex("aus", false), Vertex("wa", false), 0 );
	//
	program->AddEdge( Vertex("chi", false), Vertex("atl", false), 0 );
	program->AddEdge( Vertex("chi", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("chi", false), Vertex("chi", false), 0 );
	program->AddEdge( Vertex("chi", false), Vertex("dal", false), 0 );
	program->AddEdge( Vertex("chi", false), Vertex("den", false), 1000 );
	program->AddEdge( Vertex("chi", false), Vertex("hou", false), 0 );
	program->AddEdge( Vertex("chi", false), Vertex("wa", false), 0 );
	//
	program->AddEdge( Vertex("dal", false), Vertex("atl", false), 0 );
	program->AddEdge( Vertex("dal", false), Vertex("aus", false), 200 );
	program->AddEdge( Vertex("dal", false), Vertex("chi", false), 900 );
	program->AddEdge( Vertex("dal", false), Vertex("dal", false), 0 );
	program->AddEdge( Vertex("dal", false), Vertex("den", false), 780 );
	program->AddEdge( Vertex("dal", false), Vertex("hou", false), 0 );
	program->AddEdge( Vertex("dal", false), Vertex("wa", false), 0 );
	//
	program->AddEdge( Vertex("den", false), Vertex("atl", false), 1400 );
	program->AddEdge( Vertex("den", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("den", false), Vertex("chi", false), 1000 );
	program->AddEdge( Vertex("den", false), Vertex("dal", false), 0 );
	program->AddEdge( Vertex("den", false), Vertex("den", false), 0 );
	program->AddEdge( Vertex("den", false), Vertex("hou", false), 0 );
	program->AddEdge( Vertex("den", false), Vertex("wa", false), 0 );
	//
	program->AddEdge( Vertex("hou", false), Vertex("atl", false), 800 );
	program->AddEdge( Vertex("hou", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("hou", false), Vertex("chi", false), 0 );
	program->AddEdge( Vertex("hou", false), Vertex("dal", false), 0 );
	program->AddEdge( Vertex("hou", false), Vertex("den", false), 0 );
	program->AddEdge( Vertex("hou", false), Vertex("hou", false), 0 );
	program->AddEdge( Vertex("hou", false), Vertex("wa", false), 0 );
	//
	program->AddEdge( Vertex("wa", false), Vertex("atl", false), 600 );
	program->AddEdge( Vertex("wa", false), Vertex("aus", false), 0 );
	program->AddEdge( Vertex("wa", false), Vertex("chi", false), 0 );
	program->AddEdge( Vertex("wa", false), Vertex("dal", false), 1300 );
	program->AddEdge( Vertex("wa", false), Vertex("den", false), 0 );
	program->AddEdge( Vertex("wa", false), Vertex("hou", false), 0 );
	program->AddEdge( Vertex("wa", false), Vertex("wa", false), 0 );
}

//TEST ONE: Find path btw two Vertices and print results, if any found
void Test1()
{
	Vertex to, from;

	cout << "\nFrom Vertex: 'Austin', To Vertex: 'Washington'" << endl;
	from.Assign("aus", false);
	to.Assign("wa", false);

	cout << "\n\n-----------------------------------\nResults: " << endl;
	program->DFS(from, to);
	cout << "-----------------------------------\n\n\n" << endl;
}

//TEST TWO: Find path btw two Vertices and print results, if any found
void Test2()
{
	Vertex to, from;

	cout << "\nFrom Vertex: 'Austin', To Vertex: 'Atlanta'" << endl;
	from.Assign("aus", false);
	to.Assign("atl", false);

	cout << "\n-----------------------------------\nResults: " << endl;
	program->DFS(from, to);
	cout << "-----------------------------------\n\n\n" << endl;
}

//TEST THREE: Find path btw two Vertices and print results, if any found
void Test3()
{
	Vertex to, from;

	cout << "\nFrom Vertex: 'Washington', To Vertex: 'Austin'" << endl;
	from.Assign("wa", false);
	to.Assign("aus", false);

	cout << "\n-----------------------------------\nResults: " << endl;
	program->DFS(from, to);
	cout << "-----------------------------------\n\n\n" << endl;
}























/************************************************************************/
/*                                                                      */
/************************************************************************/



//// void Test()
//// {
//// Vertex *test = new Vertex[MAX_VERTS];

//// for (int i=0; i< MAX_VERTS; ++i) 
//// {
//// test[i].data = "test";
//// test[i].wasVisited = false;
//// }

//// cout << "\n============================================\n" << endl;
//// program->Test();
//// cout << "\n============================================\n" << endl;
//// }

